package week_02;

import java.util.ArrayDeque;
import java.util.Deque;

public class MinDepth_111_2 {
    public class Info {
        TreeNode node;
        int depth;

        public Info(TreeNode node, int depth) {
            this.node = node;
            this.depth = depth;
        }
    }

    public int minDepth(TreeNode root) {
        if(root==null) return 0;
        Deque<Info> deque = new ArrayDeque<>();
        deque.offer(new Info(root, 1));
        while (!deque.isEmpty()) {
            Info info = deque.poll();
             TreeNode node= info.node;
            int depth=info.depth;
            if (node.left == null && node.right == null) return info.depth;

            if (node.left != null) deque.offer(new Info(node.left, depth + 1));
            if (node.right != null) deque.offer(new Info(node.right, depth + 1));
        }
        return -1;
    }


    public int minDepth2(TreeNode root) {

        if (root == null) return 0;
        if (root.left == null && root.right != null) return minDepth(root.right) + 1;
        if (root.right == null && root.left != null) return minDepth(root.left) + 1;

        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
    }


}
